package leetcode_401_500;

public class LeeCode_481 {
    public static void main(String[] args) {
        System.out.println(magicalString(6));
    }
    private static int magicalString(int n) {
        if (n <= 3)
            return 1;
        StringBuilder sb = new StringBuilder("122");
        int l = 2, ans = 1;
        while (sb.length() < n){
            char last = sb.charAt(sb.length() - 1);
            char c = last == '1' ? '2' : '1';
            sb.append(c);
            if (c == '1')
                ans++;
            if (sb.length() == n)
                break;
            if (sb.charAt(l) == '2'){
                sb.append(c);
                if (c == '1')
                    ans++;
                if (sb.length() == n)
                    break;
            }
            l++;
        }
        return ans;
    }
}
